/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-01-31
 * Time: 19:48
 */
public class MyTreeNode {
    static class TreeNode {
        public char val;//数据域
        public TreeNode left;//左孩子地址
        public TreeNode right;//右孩子地址

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode root;

    //时间复杂度为O(N*N)
    public boolean isBalanced(TreeNode root) {
        //每一个节点都要判断平衡
        if(root == null) {
            return true;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.abs(leftH-rightH) < 2
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return (leftHeight >= rightHeight) ? (leftHeight+1) : (rightHeight+1);
    }

    //改进，字节面试题：如何将时间复杂度为O(n)
    public boolean isBalanced1(TreeNode root) {
        //每一个节点都要判断平衡
        return getHeight1(root) >= 0;

    }

    public int getHeight1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight1(root.left);
        //if(leftHeight < 0) return -1;
        int rightHeight = getHeight1(root.right);
        //if(rightHeight < 0) return -1; 下面就不用判断是否大于0
        if(leftHeight >=0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <= 1) {
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            return -1;
        }
    }


}